#ifndef TOOLS
#include "tools.hpp"
#endif

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <stdexcept>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <float.h>
using namespace std;

namespace _01
{
    // 1. 快速排序
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int i = l;
        sr = l - 1, br = r + 1;
        int val = v[pos];
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[sr++ + 1]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[br-- - 1]);
        }
    }
    void _QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int pos = l + rand() % (r - l + 1);
        int sr = 0, br = 0;
        Partition(v, l, r, sr, br, pos);
        _QuickSort_Process(v, l, sr);
        _QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _QuickSort_Process(v, 0, v.size() - 1);
    }

    // 2. 归并排序
    void Merge(vector<int> &v, int l, int r, int mid)
    {
        int i = l, j = mid + 1, k = 0;
        vector<int> temp(r - l + 1);
        while (i <= mid && j <= r)
        {
            if (v[i] <= v[j])
                temp[k++] = v[i++];
            else
                temp[k++] = v[j++];
        }
        while (i <= mid)
            temp[k++] = v[i++];
        while (j <= r)
            temp[k++] = v[j++];
        ::copy(temp.begin(), temp.end(), v.begin() + l);
    }
    void _MergeSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int mid = l + ((r - l) >> 1);
        _MergeSort_Process(v, l, mid);
        _MergeSort_Process(v, mid + 1, r);
        Merge(v, l, r, mid);
    }
    void MergeSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _MergeSort_Process(v, 0, v.size() - 1);
    }

    // 3. 二分查找
    int BinarySearch(const vector<int> &v, int tar)
    {
        if (v.size() <= 0)
            return -1;
        int left = 0, right = v.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = left + ((right - left) >> 1);
            if (v[mid] == tar)
                return mid;
            else if (v[mid] < tar)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }

    // 4. 两个栈实现队列
    template <class T>
    class MyQueue
    {
    private:
        stack<T> s1;
        stack<T> s2;

    public:
        void Enqueue(const T &val) { return s1.push(val); }

        T Dequeue()
        {
            if (s2.empty())
            {
                while (!s1.empty())
                {
                    s2.push(s1.top());
                    s1.pop();
                }
            }
            if (s2.empty())
                throw new logic_error("queue is empty");
            T res = s2.top();
            s2.pop();
            return res;
        }

        bool IsEmpty() { return s1.empty() && s2.empty(); }
    };

    // 5. 从尾到头打印链表 & 翻转链表
    void ReversePrintLinkedList(ListNode *head)
    {
        if (head == nullptr)
            return;
        stack<int> s;
        ListNode *p = head;
        while (p != nullptr)
        {
            s.push(p->val);
            p = p->next;
        }
        while (!s.empty())
        {
            cout << s.top() << endl;
            s.pop();
        }
    }

    void ReverseLinkedList(ListNode *&head)
    {
        if (head == nullptr || head->next == nullptr)
            return;
        ListNode *p1 = head, *p2 = head->next, *p3;
        p1->next = nullptr;
        while (p2 != nullptr)
        {
            p3 = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = p3;
        }
        head = p1;
    }

    // 6. 数组中重复数组
    bool GetSameNum(const vector<int> &v, int &res)
    {
        if (v.size() <= 1)
            return false;
        unordered_set<int> hashset;
        for (auto elem : v)
        {
            if (hashset.count(elem) != 0)
            {
                res = elem;
                return true;
            }
            hashset.insert(elem);
        }
        return false;
    }

    // 7. 二维数组查找
    bool MatrixSearch(const vector<vector<int>> &matrix, int tar)
    {
        if (matrix.size() <= 0 || matrix[0].size() <= 0)
            return false;

        int row = matrix.size(), col = matrix[0].size();
        int i = 0, j = col - 1;
        while (i < row && j >= 0)
        {
            if (tar < matrix[i][j])
                j--;
            else if (tar > matrix[i][j])
                i++;
            else
                return true;
        }
        return false;
    }

    // void Test()
    // {
    //     // QuickSort(testVector);
    //     MergeSort(testVector);
    //     cout << testVector << endl;
    //     cout << "BinarySearch 3 = " << BinarySearch(testVector, 3) << endl;

    //     MyQueue<int> q;
    //     q.Enqueue(1);
    //     q.Enqueue(2);
    //     q.Enqueue(3);
    //     q.Enqueue(4);
    //     cout << (q.IsEmpty() ? "EMPTY" : "NOT EMPTY") << endl;
    //     cout << q.Dequeue() << endl;

    //     cout << endl;
    //     ListNode n1(1);
    //     ListNode n2(2);
    //     ListNode n3(3);
    //     ListNode n4(4);
    //     n1.next = &n2;
    //     n2.next = &n3;
    //     n3.next = &n4;

    //     ReversePrintLinkedList(&n1);

    //     cout << endl;
    //     ListNode* head = &n1;
    //     ReverseLinkedList(head);
    //     cout << head << endl;
    // }

    void Test()
    {
        int sameNum = 0;
        bool res = GetSameNum(testVector, sameNum);
        if (res)
            cout << sameNum << endl;
        else
            cout << "DO NOT HAVE SAME ELEM" << endl;

        vector<vector<int>> matrix =
            {
                {1, 2, 3, 4, 5},
                {3, 4, 5, 6, 7},
                {4, 5, 8, 9, 10},
            };
        cout << MatrixSearch(matrix, 0) << endl;
    }
}

namespace _02
{
    // 1. 插入排序
    void InsertSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        for (size_t i = 1; i < v.size(); i++)
        {
            for (size_t j = i; j > 0 && v[j] < v[j - 1]; j--)
                Swap(v[j], v[j - 1]);
        }
    }

    // 2. 归并排序
    void Merge(vector<int> &v, int l, int r, int mid)
    {
        int i = l, j = mid + 1;
        vector<int> temp;
        while (i <= mid && j <= r)
        {
            if (v[i] <= v[j])
                temp.push_back(v[i++]);
            else
                temp.push_back(v[j++]);
        }
        while (i <= mid)
            temp.push_back(v[i++]);
        while (j <= r)
            temp.push_back(v[j++]);
        ::copy(temp.begin(), temp.end(), v.begin() + l);
    }
    void _MergeSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int mid = l + ((r - l) >> 1);
        _MergeSort_Process(v, l, mid);
        _MergeSort_Process(v, mid + 1, r);
        Merge(v, l, r, mid);
    }
    void MergeSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _MergeSort_Process(v, 0, v.size() - 1);
    }

    // 3. 快速排序
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int i = l;
        sr = l - 1, br = r + 1;
        int val = v[pos];
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[sr++ + 1]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[br-- - 1]);
        }
    }
    void _QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int pos = l + rand() % (r - l + 1);
        int sr = 0, br = 0;
        Partition(v, l, r, sr, br, pos);
        _QuickSort_Process(v, l, sr);
        _QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _QuickSort_Process(v, 0, v.size() - 1);
    }

    // 4. 二分查找
    int BinarySearch(const vector<int> &v, int tar)
    {
        int left = 0, right = v.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = left + ((right - left) >> 1);
            if (v[mid] < tar)
                left = mid + 1;
            else if (v[mid] > tar)
                right = mid - 1;
            else
                return mid;
        }
        return -1;
    }

    // 5. 二叉树的遍历（递归版本）
    template <typename _Action>
    void PreOrder_Recursive(BiTreeNode *root, _Action action)
    {
        if (root == nullptr)
            return;
        action(root->val);
        PreOrder_Recursive(root->lchild, action);
        PreOrder_Recursive(root->rchild, action);
    }
    template <typename _Action>
    void InOrder_Recursive(BiTreeNode *root, _Action action)
    {
        if (root == nullptr)
            return;
        InOrder_Recursive(root->lchild, action);
        action(root->val);
        InOrder_Recursive(root->rchild, action);
    }
    template <typename _Action>
    void PostOrder_Recursive(BiTreeNode *root, _Action action)
    {
        if (root == nullptr)
            return;
        PostOrder_Recursive(root->lchild, action);
        PostOrder_Recursive(root->rchild, action);
        action(root->val);
    }

    // 6. 二叉树遍历（非递归）
    template <typename _Action>
    void PreOrder(BiTreeNode *root, _Action action)
    {
        if (root == nullptr)
            return;
        stack<BiTreeNode *> s;
        s.push(root);
        BiTreeNode *cur;
        while (!s.empty())
        {
            cur = s.top();
            s.pop();
            action(cur->val);
            if (cur->rchild != nullptr)
                s.push(cur->rchild);
            if (cur->lchild != nullptr)
                s.push(cur->lchild);
        }
    }
    template <typename _Action>
    void PostOrder(BiTreeNode *root, _Action action)
    {
        if (root == nullptr)
            return;
        stack<BiTreeNode *> s1;
        stack<BiTreeNode *> s2;
        s1.push(root);
        BiTreeNode *cur;
        while (!s1.empty())
        {
            cur = s1.top();
            s1.pop();
            s2.push(cur);
            if (cur->lchild != nullptr)
                s1.push(cur->lchild);
            if (cur->rchild != nullptr)
                s1.push(cur->rchild);
        }
        while (!s2.empty())
        {
            cur = s2.top();
            s2.pop();
            action(cur->val);
        }
    }
    template <typename _Action>
    void InOrder(BiTreeNode *root, _Action action)
    {
        if (root == nullptr)
            return;
        stack<BiTreeNode *> s;
        while (!s.empty() || root != nullptr)
        {
            if (root != nullptr)
            {
                s.push(root);
                root = root->lchild;
            }
            else
            {
                root = s.top();
                s.pop();
                action(root->val);
                root = root->rchild;
            }
        }
    }

    // 7. 判断一棵树是否为平衡二叉树
    struct IsBST_RType
    {
        int height;
        bool isBST;

        IsBST_RType(int height, bool isBST) : height(height), isBST(isBST) {}
    };
    IsBST_RType _IsBST_Process(BiTreeNode *root)
    {
        if (root == nullptr)
            return IsBST_RType(0, true);

        IsBST_RType lData = _IsBST_Process(root->lchild);
        IsBST_RType rData = _IsBST_Process(root->rchild);

        int height = 1 + ::max(lData.height, rData.height);
        bool isBST = (lData.isBST && rData.isBST && (::abs(lData.height - rData.height) <= 1));

        return IsBST_RType(height, isBST);
    }
    bool IsBST(BiTreeNode *root)
    {
        return _IsBST_Process(root).isBST;
    }

    // 8. 机器人移动范围问题
    int SumDigit(int num)
    {
        int sum = 0;
        while (num > 0)
        {
            sum += (num % 10);
            num /= 10;
        }
        return sum;
    }
    int _RobotMove_Process(int m, int n, int i, int j, int k, vector<vector<bool>> &visit)
    {
        int res = 0;
        if (i >= 0 && i < m && j >= 0 && j < n && ((SumDigit(i) + SumDigit(j)) <= k) && !visit[i][j])
        {
            visit[i][j] = true;
            res = 1 + _RobotMove_Process(m, n, i - 1, j, k, visit) + _RobotMove_Process(m, n, i + 1, j, k, visit) + _RobotMove_Process(m, n, i, j - 1, k, visit) + _RobotMove_Process(m, n, i, j + 1, k, visit);
        }
        return res;
    }
    int RobotMove(int m, int n, int k)
    {
        if (m <= 0 || n <= 0)
            return 0;
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        return _RobotMove_Process(m, n, 0, 0, k, visit);
    }

    void Test()
    {
        // InsertSort(testVector);
        // MergeSort(testVector);
        QuickSort(testVector);
        cout << testVector << endl;
        cout << BinarySearch(testVector, 3) << endl;

        cout << endl;
        BiTreeNode n1(1);
        BiTreeNode n2(2);
        BiTreeNode n3(3);
        BiTreeNode n4(4);
        BiTreeNode n5(5);
        n1.lchild = &n2;
        n1.rchild = &n3;
        n2.lchild = &n4;
        n2.rchild = &n5;

        PreOrder_Recursive(&n1, PrintFunction);
        cout << endl;
        InOrder_Recursive(&n1, PrintFunction);
        cout << endl;
        PostOrder_Recursive(&n1, PrintFunction);
        cout << endl;

        PreOrder(&n1, PrintFunction);
        cout << endl;
        PostOrder(&n1, PrintFunction);
        cout << endl;
        InOrder(&n1, PrintFunction);

        cout << endl;
        cout << IsBST(&n1) << endl;

        cout << RobotMove(20, 20, 5) << endl;
    }
}

namespace _03
{
    // 1. 冒泡排序  O(n^2) | O(1)
    void BubbleSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        for (int i = v.size() - 1; i > 0; i--)
        {
            bool isSwap = false;
            for (int j = 0; j < i; j++)
            {
                if (v[j] > v[j + 1])
                {
                    Swap(v[j], v[j + 1]);
                    isSwap = true;
                }
            }
            if (!isSwap)
                break;
        }
    }

    // 2. 插入排序  O(n^2) | O(1)
    void InsertSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        int len = v.size();
        for (int i = 1; i < len; i++)
        {
            for (int j = i; j > 0 && v[j] < v[j - 1]; j--)
                Swap(v[j], v[j - 1]);
        }
    }

    // 3. 归并排序  O(nlogn) | O(n)
    void Merge(vector<int> &v, int l, int r, int mid)
    {
        vector<int> temp((r - l + 1), 0);
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r)
        {
            if (v[i] <= v[j])
                temp[k++] = v[i++];
            else
                temp[k++] = v[j++];
        }
        while (i <= mid)
            temp[k++] = v[i++];
        while (j <= r)
            temp[k++] = v[j++];
        ::copy(temp.begin(), temp.end(), v.begin() + l);
    }
    void _MergeSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int mid = l + ((r - l) >> 1);
        _MergeSort_Process(v, l, mid);
        _MergeSort_Process(v, mid + 1, r);
        Merge(v, l, r, mid);
    }
    void MergeSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _MergeSort_Process(v, 0, v.size() - 1);
    }

    // 4. 快速排序  O(nlogn) | O(logn)
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int val = v[pos];
        sr = l - 1, br = r + 1;
        int i = l;
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[sr++ + 1]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[br-- - 1]);
        }
    }
    void _QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l < r)
        {
            int pos = l + (rand() % (r - l + 1));
            int sr = 0, br = 0;
            Partition(v, l, r, sr, br, pos);
            _QuickSort_Process(v, l, sr);
            _QuickSort_Process(v, br, r);
        }
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        srand((unsigned int)time(nullptr));
        _QuickSort_Process(v, 0, v.size() - 1);
    }

    // 5. 堆排序    O(nlogn) | O(1)
    void Heapify(vector<int> &v, int heapSize, int i)
    {
        int left = 2 * i + 1, right = left + 1;
        while (left < heapSize)
        {
            int maxIndex = (right < heapSize && v[right] > v[left]) ? right : left;
            maxIndex = (v[i] > v[maxIndex]) ? i : maxIndex;
            if (i == maxIndex)
                return;
            Swap(v[i], v[maxIndex]);
            i = maxIndex;
            left = 2 * i + 1;
            right = left + 1;
        }
    }
    void HeapSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        int heapSize = v.size();
        // 构建堆
        for (int i = heapSize - 1; i >= 0; i--)
            Heapify(v, heapSize, i);
        // 堆化
        while (heapSize > 0)
        {
            Swap(v[0], v[--heapSize]);
            Heapify(v, heapSize, 0);
        }
    }

    // 6. 取得一个整数的所有二进制1个数
    int SumDigitOne(int num)
    {
        int count = 0;
        int d = 0x1;
        while (d != 0)
        {
            if ((num & d) != 0)
                count++;
            d <<= 1;
        }
        return count;
    }

    void Test()
    {
        // BubbleSort(testVector);
        // InsertSort(testVector);
        // MergeSort(testVector);
        // QuickSort(testVector);
        HeapSort(testVector);
        cout << testVector << endl;

        cout << SumDigitOne(-1) << endl;
    }
}

namespace _04
{
    // 1. 快速排序
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int val = v[pos];
        sr = l - 1, br = r + 1;
        int i = l;
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[sr++ + 1]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[br-- - 1]);
        }
    }
    void _QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int pos = l + rand() % (r - l + 1);
        int sr = 0, br = 0;
        Partition(v, l, r, sr, br, pos);
        _QuickSort_Process(v, l, sr);
        _QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _QuickSort_Process(v, 0, v.size() - 1);
    }

    // 2. 归并排序
    void Merge(vector<int> &v, int l, int r, int mid)
    {
        vector<int> temp;
        int i = l, j = mid + 1;
        while (i <= mid && j <= r)
        {
            if (v[i] <= v[j])
                temp.push_back(v[i++]);
            else
                temp.push_back(v[j++]);
        }
        while (i <= mid)
            temp.push_back(v[i++]);
        while (j <= r)
            temp.push_back(v[j++]);
        ::copy(temp.begin(), temp.end(), v.begin() + l);
    }
    void _MergeSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int mid = l + ((r - l) >> 1);
        _MergeSort_Process(v, l, mid);
        _MergeSort_Process(v, mid + 1, r);
        Merge(v, l, r, mid);
    }
    void MergeSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _MergeSort_Process(v, 0, v.size() - 1);
    }

    // 3. 二分查找
    int BinarySearch(const vector<int> &v, int tar)
    {
        if (v.size() == 0)
            return -1;
        int l = 0, r = v.size() - 1;
        int mid;
        while (l <= r)
        {
            mid = l + ((r - l) >> 1);
            if (v[mid] < tar)
                l = mid + 1;
            else if (v[mid] > tar)
                r = mid - 1;
            else
                return mid;
        }
        return -1;
    }

    // 4. 两个栈实现队列
    template <class T>
    class MyQueue
    {
    private:
        stack<T> s1;
        stack<T> s2;

    public:
        void Enqueue(const T &val)
        {
            s1.push(val);
        }

        T Dequeue()
        {
            if (s2.empty())
            {
                while (!s1.empty())
                {
                    s2.push(s1.top());
                    s1.pop();
                }
            }
            if (s2.empty())
                throw new logic_error("queue is empty");
            T res = s2.top();
            s2.pop();
            return res;
        }
    };

    // 5. 爬楼梯
    int Step_1(int n)
    {
        if (n <= 0)
            return 0;
        if (n <= 1)
            return 1;
        if (n == 2)
            return 2;
        return Step_1(n - 1) + Step_1(n - 2);
    }
    int Step_2(int n)
    {
        if (n <= 0)
            return 0;
        else if (n == 1)
            return 1;
        else if (n == 2)
            return 2;

        int *resArr = new int[n + 1];
        resArr[1] = 1;
        resArr[2] = 2;
        for (int i = 3; i <= n; i++)
        {
            resArr[i] = resArr[i - 1] + resArr[i - 2];
        }
        int res = resArr[n];
        delete[] resArr;
        resArr = nullptr;

        return res;
    }

    // 6. 翻转链表
    ListNode *ReverseLinkedList(ListNode *head)
    {
        if (head == nullptr)
            return nullptr;
        ListNode *pPre = head, *pCur = head->next, *pNext;
        pPre->next = nullptr;
        while (pCur != nullptr)
        {
            pNext = pCur->next;
            pCur->next = pPre;
            pPre = pCur;
            pCur = pNext;
        }
        return pPre;
    }

    // 7. 复杂链表复制
    RandListNode *RandLinkedListCopy(RandListNode *head)
    {
        if (head == nullptr)
            return nullptr;

        // 创建结点 并构建映射表
        unordered_map<RandListNode *, RandListNode *> nodeMap;
        RandListNode *p = head;
        while (p != nullptr)
        {
            nodeMap.insert(make_pair(p, new RandListNode(p->val)));
            p = p->next;
        }

        p = head;
        while (p != nullptr)
        {
            nodeMap[p]->rand = nodeMap[p->rand];
            nodeMap[p]->next = nodeMap[p->next];
            p = p->next;
        }

        return nodeMap[head];
    }

    void Test()
    {
        cout << testVector << endl;
        // QuickSort(testVector);
        MergeSort(testVector);
        cout << testVector << endl;

        cout << BinarySearch(testVector, 2) << endl;

        MyQueue<int> q;
        q.Enqueue(1);
        q.Enqueue(2);
        q.Enqueue(3);
        cout << q.Dequeue() << endl;
        cout << q.Dequeue() << endl;
        cout << q.Dequeue() << endl;

        cout << "======== STEP1 ========" << endl;
        clock_t startTime = clock();
        cout << Step_1(40) << endl;
        cout << (clock() - startTime) << "ms" << endl;
        cout << "======== STEP2 ========" << endl;
        startTime = clock();
        cout << Step_2(40) << endl;
        cout << (clock() - startTime) << "ms" << endl;

        ListNode n1(1);
        ListNode n2(2);
        ListNode n3(3);
        ListNode n4(4);
        ListNode n5(5);
        n1.next = &n2;
        n2.next = &n3;
        n3.next = &n4;
        n4.next = &n5;

        ListNode *res = ReverseLinkedList(&n1);
        cout << res << endl;

        RandListNode rn1(1);
        RandListNode rn2(2);
        RandListNode rn3(3);
        rn1.next = &rn2;
        rn2.next = &rn3;
        rn1.rand = &rn3;
        rn2.rand = &rn1;

        RandListNode *copy = RandLinkedListCopy(&rn1);
    }
}

namespace _05
{
    // 1. 插入排序
    void InsertSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        int len = v.size();
        for (int i = 1; i < len; i++)
        {
            for (int j = i; j > 0 && v[j] < v[j - 1]; j--)
                Swap(v[j], v[j - 1]);
        }
    }

    // 2. 快速排序
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int val = v[pos];
        int i = l;
        sr = l - 1, br = r + 1;
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[sr++ + 1]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[br-- - 1]);
        }
    }
    void _QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int pos = l + (rand() % (r - l + 1));
        int sr = 0, br = 0;
        Partition(v, l, r, sr, br, pos);
        _QuickSort_Process(v, l, sr);
        _QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _QuickSort_Process(v, 0, v.size() - 1);
    }

    // 3. 二分查找
    int BinarySearch(vector<int> &v, int tar)
    {
        if (v.size() <= 0)
            return -1;
        int left = 0, right = v.size() - 1, mid;
        while (left <= right)
        {
            mid = left + ((right - left) >> 1);
            if (v[mid] < tar)
                left = mid + 1;
            else if (v[mid] > tar)
                right = mid - 1;
            else
                return mid;
        }
        return -1;
    }

    // 4. 二叉树的递归遍历
    void PreOrder_Recursive(BiTreeNode *root, void (*action)(int))
    {
        if (root == nullptr)
            return;
        action(root->val);
        PreOrder_Recursive(root->lchild, action);
        PreOrder_Recursive(root->rchild, action);
    }
    void InOrder_Recursive(BiTreeNode *root, void (*action)(int))
    {
        if (root == nullptr)
            return;
        InOrder_Recursive(root->lchild, action);
        action(root->val);
        InOrder_Recursive(root->rchild, action);
    }
    void PostOrder_Recursive(BiTreeNode *root, void (*action)(int))
    {
        if (root == nullptr)
            return;
        PostOrder_Recursive(root->lchild, action);
        PostOrder_Recursive(root->rchild, action);
        action(root->val);
    }

    // 5. 二叉树的非递归遍历
    void PreOrder(BiTreeNode *root, void (*action)(int))
    {
        if (root == nullptr)
            return;
        stack<BiTreeNode *> s;
        s.push(root);
        BiTreeNode *cur;
        while (!s.empty())
        {
            cur = s.top();
            s.pop();
            action(cur->val);
            if (cur->rchild != nullptr)
                s.push(cur->rchild);
            if (cur->lchild != nullptr)
                s.push(cur->lchild);
        }
    }
    void PostOrder(BiTreeNode *root, void (*action)(int))
    {
        if (root == nullptr)
            return;
        stack<BiTreeNode *> s1;
        stack<BiTreeNode *> s2;
        s1.push(root);
        BiTreeNode *cur;
        while (!s1.empty())
        {
            cur = s1.top();
            s1.pop();
            s2.push(cur);
            if (cur->lchild != nullptr)
                s1.push(cur->lchild);
            if (cur->rchild != nullptr)
                s1.push(cur->rchild);
        }
        while (!s2.empty())
        {
            cur = s2.top();
            s2.pop();
            action(cur->val);
        }
    }
    void InOrder(const BiTreeNode *root, void (*action)(int))
    {
        stack<const BiTreeNode *> s;
        while (!s.empty() || root != nullptr)
        {
            if (root != nullptr)
            {
                s.push(root);
                root = root->lchild;
            }
            else
            {
                root = s.top();
                s.pop();
                action(root->val);
                root = root->rchild;
            }
        }
    }

    // 6. 二叉树的层次遍历
    void BST(const BiTreeNode *root, void (*action)(int))
    {
        if (root == nullptr)
            return;
        queue<const BiTreeNode *> q;
        q.push(root);
        const BiTreeNode *cur;
        while (!q.empty())
        {
            cur = q.front();
            q.pop();
            action(cur->val);
            if (cur->lchild != nullptr)
                q.push(cur->lchild);
            if (cur->rchild != nullptr)
                q.push(cur->rchild);
        }
    }

    // 7. 判断二叉树是否为完全二叉树
    bool IsCBT(const BiTreeNode *root)
    {
        if (root == nullptr)
            return false;
        queue<const BiTreeNode *> q;
        q.push(root);
        const BiTreeNode *cur;
        bool flag = false;
        while (!q.empty())
        {
            cur = q.front();
            q.pop();

            // 左空右有 FALSE
            if (cur->lchild == nullptr && cur->rchild != nullptr)
                return false;

            // 第一次左右子树不双全
            if (!flag)
            {
                if (cur->lchild == nullptr || cur->rchild == nullptr)
                    flag = true;
            }
            // 后续结点均为叶子结点
            else
            {
                if (cur->lchild != nullptr || cur->rchild != nullptr)
                    return false;
            }

            if (cur->lchild != nullptr)
                q.push(cur->lchild);
            if (cur->rchild != nullptr)
                q.push(cur->rchild);
        }

        return true;
    }

    // 8. 找两二叉树的最小公共祖先结点
    void GetFatherMap(BiTreeNode *root, unordered_map<BiTreeNode *, BiTreeNode *> &fatherMap)
    {
        if (root->lchild != nullptr)
        {
            fatherMap.insert(make_pair(root->lchild, root));
            GetFatherMap(root->lchild, fatherMap);
        }
        if (root->rchild != nullptr)
        {
            fatherMap.insert(make_pair(root->rchild, root));
            GetFatherMap(root->rchild, fatherMap);
        }
    }
    BiTreeNode *GetLowestAncestor(BiTreeNode *root, BiTreeNode *n1, BiTreeNode *n2)
    {
        if (root == nullptr || n1 == nullptr || n2 == nullptr)
            return nullptr;

        // 构建父节点指向
        unordered_map<BiTreeNode *, BiTreeNode *> fatherMap;
        GetFatherMap(root, fatherMap);
        fatherMap.insert(make_pair(root, nullptr)); // 根结点的父节点指向空

        // 构建n1的路径
        unordered_set<BiTreeNode *> path;
        BiTreeNode *cur = n1;
        while (cur != nullptr)
        {
            path.insert(cur);
            cur = fatherMap[cur];
        }

        // 查看n2路径与n1的相交位置
        cur = n2;
        while (cur != nullptr)
        {
            if (path.count(cur) != 0)
                return cur;
            cur = fatherMap[cur];
        }

        return nullptr;
    }

    void Test()
    {
        vector<int> testVector(1000);
        for (int i = 1000; i > 0; i--)
            testVector[1000 - i] = i;
        clock_t startTime = clock();
        QuickSort(testVector);
        // cout << testVector << endl;
        cout << (clock() - startTime) << "ms" << endl;

        cout << BinarySearch(testVector, 333) << endl;
        cout << BinarySearch(testVector, 1043) << endl;

        BiTreeNode r1(1);
        BiTreeNode r2(2);
        BiTreeNode r3(3);
        BiTreeNode r4(4);
        r1.lchild = &r2;
        r1.rchild = &r3;
        r2.lchild = &r4;

        cout << endl;
        PreOrder_Recursive(&r1, [](int val) -> void
                           { cout << val << endl; });
        cout << endl;
        InOrder_Recursive(&r1, [](int val) -> void
                          { cout << val << endl; });
        cout << endl;
        PostOrder_Recursive(&r1, [](int val) -> void
                            { cout << val << endl; });
        cout << endl;
        PreOrder(&r1, [](int val) -> void
                 { cout << val << endl; });
        cout << endl;
        PostOrder(&r1, [](int val) -> void
                  { cout << val << endl; });
        cout << endl;
        InOrder(&r1, [](int val) -> void
                { cout << val << endl; });
        cout << endl;
        BST(&r1, [](int val) -> void
            { cout << val << endl; });

        cout << "isCBT = " << (IsCBT(&r1) ? "TRUE" : "FALSE") << endl;
        BiTreeNode *res = GetLowestAncestor(&r1, &r3, &r4);
    }
}

namespace _06
{
    // 1. 归并排序
    void Merge(vector<int> &v, int l, int r, int mid)
    {
        int i = l, j = mid + 1;
        vector<int> temp;
        while (i <= mid && j <= r)
        {
            if (v[i] <= v[j])
                temp.push_back(v[i++]);
            else
                temp.push_back(v[j++]);
        }
        while (i <= mid)
            temp.push_back(v[i++]);
        while (j <= r)
            temp.push_back(v[j++]);
        ::copy(temp.begin(), temp.end(), v.begin() + l);
    }
    void _MergeSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int mid = l + ((r - l) >> 1);
        _MergeSort_Process(v, l, mid);
        _MergeSort_Process(v, mid + 1, r);
        Merge(v, l, r, mid);
    }
    void MergeSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _MergeSort_Process(v, 0, v.size() - 1);
    }

    // 2. 快速排序
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int i = l;
        int val = v[pos];
        sr = l - 1, br = r + 1;
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[sr++ + 1]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[br-- - 1]);
        }
    }
    void _QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int pos = l + (rand() % (r - l + 1));
        int sr = 0, br = 0;
        Partition(v, l, r, sr, br, pos);
        _QuickSort_Process(v, l, sr);
        _QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        srand((unsigned int)time(nullptr));
        _QuickSort_Process(v, 0, v.size() - 1);
    }

    // 3. 替换空格
    void ReplaceSpace(char *str)
    {
        if (str == nullptr)
            return;

        // 检查一共有多少空格
        int len = strlen(str);
        int spaceCount = 0;
        for (int i = 0; i < len; i++)
        {
            if (str[i] == ' ')
                spaceCount++;
        }

        // 计算新的字符串大小
        int i = len,
            j = len + spaceCount * 2;
        while (i >= 0)
        {
            if (str[i] != ' ')
                str[j--] = str[i--];
            else
            {
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '%';
                i--;
            }
        }
    }

    // 4. 二分查找
    int BinarySearch(const vector<int> &v, int tar)
    {
        if (v.size() == 0)
            return -1;

        int left = 0, right = v.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = left + ((right - left) >> 1);
            if (v[mid] < tar)
                left = mid + 1;
            else if (v[mid] > tar)
                right = mid - 1;
            else
                return mid;
        }

        return -1;
    }
    int BinarySearch(const vector<double> &v, double tar, double precision = DBL_EPSILON)
    {
        if (v.size() == 0)
            return -1;
        int left = 0, right = v.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = left + ((right - left) >> 1);
            if (fabs(v[mid] - tar) <= precision) // =
                return mid;
            else if (v[mid] - tar > precision) // >
                right = mid - 1;
            else // <
                left = mid + 1;
        }
        return -1;
    }

    // 5. 数组中重复数字
    bool RepeatNum(const vector<int> &v, int &res)
    {
        unordered_set<int> hashset;
        for (int i = 0; i < v.size(); i++)
        {
            if (hashset.count(v[i]) == 0)
                hashset.insert(v[i]);
            else
            {
                res = v[i];
                return true;
            }
        }
        return false;
    }

    // 6. 二维数组中的查找
    bool FindMatrix(const vector<vector<int>> &matrix, int tar)
    {
        if (matrix.size() <= 1 || matrix[0].size() <= 1)
            return false;
        int row = matrix.size();
        int col = matrix[0].size();
        // 从右上角查找
        int i = 0, j = col - 1;
        while (i >= 0 && i < row && j >= 0 && j < col)
        {
            if (matrix[i][j] < tar)
                i++;
            else if (matrix[i][j] > tar)
                j--;
            else
                return true;
        }
        return false;
    }

    // 7. 翻转链表
    ListNode *ReverseLinkedList(ListNode *head)
    {
        if (head == nullptr)
            return nullptr;
        ListNode *pre = head, *cur = head->next, *next;
        pre->next = nullptr;
        while (cur != nullptr)
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    // 8. 斐波那契数列
    int Fib_Recursive(int n)
    {
        if (n <= 0)
            return 0;
        if (n == 1 || n == 2)
            return 1;
        return Fib_Recursive(n - 1) + Fib_Recursive(n - 2);
    }
    int Fib(int n)
    {
        if (n <= 0)
            return 0;
        if (n == 1 || n == 2)
            return 1;
        int minusOne = 1;
        int minusTwo = 1;
        int res = 0;
        for (int i = 3; i <= n; i++)
        {
            res = minusOne + minusTwo;
            minusTwo = minusOne;
            minusOne = res;
        }
        return res;
    }

    void Test()
    {
        testVector = vector<int>();
        for (int i = 0; i < 10000; i++)
            testVector.push_back(i);
        testVector[0] = 9999;

        clock_t startTime = clock();
        QuickSort(testVector);
        // cout << testVector << endl;
        cout << (clock() - startTime) << "ms" << endl;

        char str[100] = "I am YOU";
        ReplaceSpace(str);
        cout << str << endl;

        cout << BinarySearch(testVector, 11) << endl;

        vector<double> dv{1.1, 2.3, 5.4, 6.6, 9.0, 11.12};
        cout << BinarySearch(dv, 2.3) << endl;

        cout << endl;
        int res = 0;
        RepeatNum(testVector, res);
        cout << res << endl;

        vector<vector<int>> matrix{
            {1, 2, 3, 4, 5},
            {3, 5, 6, 7, 8},
            {4, 6, 7, 9, 10},
        };
        cout << (FindMatrix(matrix, 0) ? "TRUE" : "FALSE") << endl;

        ListNode n1(1);
        ListNode n2(2);
        ListNode n3(3);
        ListNode n4(4);
        n1.next = &n2;
        n2.next = &n3;
        n3.next = &n4;
        ListNode *resNode = ReverseLinkedList(&n1);
        cout << resNode << endl;

        startTime = clock();
        cout << "Fib_Recursive(40) = " << Fib_Recursive(40) << endl;
        cout << (clock() - startTime) << "ms" << endl;
        startTime = clock();
        cout << "Fib(40) = " << Fib(40) << endl;
        cout << (clock() - startTime) << "ms" << endl;
    }
}

namespace _07
{
    // 1. 插入排序
    void InsertSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        for (int i = 1; i < v.size(); i++)
        {
            for (int j = i; j > 0 && v[j] < v[j - 1]; j--)
                Swap(v[j], v[j - 1]);
        }
    }

    // 2. 快速排序
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int val = v[pos];
        int i = l;
        sr = l - 1, br = r + 1;
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[sr++ + 1]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[br-- - 1]);
        }
    }
    void _QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int sr = 0, br = 0;
        int pos = l + (rand() % (r - l + 1));
        Partition(v, l, r, sr, br, pos);
        _QuickSort_Process(v, l, sr);
        _QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        srand((unsigned int)time(NULL));
        _QuickSort_Process(v, 0, v.size() - 1);
    }

    // 3. 归并排序
    void Merge(vector<int> &v, int l, int r, int mid)
    {
        int i = l, j = mid + 1;
        vector<int> temp(r - l + 1);
        int k = 0;
        while (i <= mid && j <= r)
        {
            if (v[i] <= v[j])
                temp[k++] = v[i++];
            else
                temp[k++] = v[j++];
        }
        while (i <= mid)
            temp[k++] = v[i++];
        while (j <= r)
            temp[k++] = v[j++];
        ::copy(temp.begin(), temp.end(), v.begin() + l);
    }
    void _MergeSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int mid = l + ((r - l) >> 1);
        _MergeSort_Process(v, l, mid);
        _MergeSort_Process(v, mid + 1, r);
        Merge(v, l, r, mid);
    }
    void MergeSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _MergeSort_Process(v, 0, v.size() - 1);
    }

    // 4. 二分查找
    int BinarySearch(const vector<int> &v, int tar)
    {
        if (v.size() == 0)
            return -1;
        int left = 0, right = v.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = left + ((right - left) >> 1);
            if (v[mid] < tar)
                left = mid + 1;
            else if (v[mid] > tar)
                right = mid - 1;
            else
                return mid;
        }
        return -1;
    }

    // 5. 树的子结构
    bool DoesTree1HaveTree2(BiTreeNode *root1, BiTreeNode *root2)
    {
        if (root2 == nullptr)
            return true;
        if (root1 == nullptr)
            return false;
        if (root1->val != root2->val)
            return false;
        return DoesTree1HaveTree2(root1->lchild, root2->lchild) && DoesTree1HaveTree2(root1->rchild, root2->rchild);
    }
    bool SubTree(BiTreeNode *root1, BiTreeNode *root2)
    {
        bool res = false;
        if (root1 != nullptr && root2 != nullptr)
        {
            if (root1->val == root2->val)
                res = DoesTree1HaveTree2(root1, root2);
            if (!res)
                res = SubTree(root1->lchild, root2);
            if (!res)
                res = SubTree(root1->rchild, root2);
        }
        return res;
    }

    // 6. 二叉树镜像
    void Mirror(BiTreeNode *root)
    {
        if (root == nullptr)
            return;
        Mirror(root->lchild);
        Mirror(root->rchild);
        // 左右互换
        BiTreeNode *temp = root->lchild;
        root->lchild = root->rchild;
        root->rchild = temp;
    }

    // 7. 二叉树对称
    bool IsSymmetrical(BiTreeNode *root1, BiTreeNode *root2)
    {
        if (root1 == nullptr && root2 == nullptr)
            return true;
        if (root1 == nullptr || root2 == nullptr)
            return false;
        if (root1->val != root2->val)
            return false;
        return IsSymmetrical(root1->lchild, root2->rchild) && IsSymmetrical(root1->rchild, root1->lchild);
    }
    bool IsSymmetrical(BiTreeNode *root)
    {
        return IsSymmetrical(root, root);
    }

    // 8. 调整数组至奇数在偶数前
    void OddBeforeEven(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        int oddRange = -1;
        for (int i = 0; i < (int)v.size(); i++)
        {
            if ((v[i] & 0x1) == 1) // 奇数
                Swap(v[i], v[oddRange++ + 1]);
        }
    }

    // 9. 数的三次方根
    double CubeRoot(double tar, double precision = DBL_EPSILON)
    {
        double l = -100, r = 100;
        double mid;
        while (r - l > precision)
        {
            mid = (r + l) / 2;
            if (mid * mid * mid <= tar)
                l = mid;
            else
                r = mid;
        }
        return l;
    }

    void Test()
    {
        MergeSort(testVector);
        cout << testVector << endl;

        cout << BinarySearch(testVector, 2) << endl;

        cout << CubeRoot(8, 1e-4) << endl;

        BiTreeNode r1(1);
        BiTreeNode r2(2);
        BiTreeNode r3(3);
        BiTreeNode r4(4);
        BiTreeNode r5(5);
        r1.lchild = &r2;
        r1.rchild = &r3;
        r2.lchild = &r4;
        r2.rchild = &r5;

        cout << (SubTree(&r1, &r2) ? "TRUE" : "FALSE") << endl;

        Mirror(&r1);

        cout << (IsSymmetrical(&r1) ? "TRUE" : "FALSE") << endl;

        OddBeforeEven(testVector);
        cout << testVector << endl;
    }
}

namespace _08
{
    // 1. 快速排序
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int val = v[pos];
        sr = l - 1, br = r + 1;
        int i = l;
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[sr++ + 1]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[br-- - 1]);
        }
    }
    void _QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int sr = 0, br = 0;
        int pos = l + (rand() % (r - l + 1));
        Partition(v, l, r, sr, br, pos);
        _QuickSort_Process(v, l, sr);
        _QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        srand((unsigned int)time(NULL));
        _QuickSort_Process(v, 0, v.size() - 1);
    }

    // 2. 堆排序
    void Heapify(vector<int> &v, int i, int heapSize)
    {
        int l = 2 * i + 1, r = l + 1;
        while (l < heapSize)
        {
            int maxIndex = (r < heapSize && v[r] > v[l]) ? r : l;
            maxIndex = v[maxIndex] < v[i] ? i : maxIndex;
            if (maxIndex == i)
                return;
            Swap(v[maxIndex], v[i]);
            i = maxIndex;
            l = 2 * i + 1;
            r = l + 1;
        }
    }
    void HeapSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        int heapSize = v.size();

        for (int i = heapSize - 1; i >= 0; i--)
            Heapify(v, i, heapSize);

        while (heapSize > 0)
        {
            Swap(v[0], v[--heapSize]);
            Heapify(v, 0, heapSize);
        }
    }

    // 3. 删除链表的结点
    void DeleteNode(ListNode *head, ListNode *node)
    {
        // 空结点
        if (head == nullptr || node == nullptr)
            return;

        // 尾结点 O(n)
        if (node->next == nullptr)
        {
            ListNode *p = head;
            while (p->next != node)
                p = p->next;
            p->next = nullptr;
            delete node;
            node = nullptr;
        }
        // 正常情况 O(1)
        else
        {
            ListNode *pNext = node->next;
            node->val = pNext->val;
            node->next = pNext->next;
            delete pNext;
            pNext = nullptr;
        }
    }

    // 4. 调整数组顺序使奇在偶前
    void OddBeforeEven(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        int oddRange = -1;
        for (int i = 0; i < (int)v.size(); i++)
        {
            if ((v[i] & 0x1) == 1) // 奇数
                Swap(v[i], v[oddRange++ + 1]);
        }
    }

    // 5. 链表中倒数第k个结点
    ListNode *GetNodeFromTail(ListNode *head, int k)
    {
        // 传入负值
        if (k < 0)
            throw new logic_error("k cannot be negative");
        // 倒数第0个结点
        else if (k == 0 || head == nullptr)
            return nullptr;

        // 快指针先走k步
        ListNode *fast = head, *slow = head;
        int i = 0;
        for (i = 0; i < k && fast != nullptr; i++)
            fast = fast->next;
        // k步数大于链表长度
        if (i < k)
            throw new logic_error("k is greater than the length of linkedlist");

        // 快慢指针同时移动至快指针为空
        while (fast != nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }

    // 6. 合并两个排序链表
    ListNode *MergeLinkedList(ListNode *head1, ListNode *head2)
    {
        // 空头结点
        if (head1 == nullptr || head2 == nullptr)
            return head1 ? head1 : head2; // head1 ?? head2

        ListNode *dummyHead = new ListNode(0);
        ListNode *p = head1, *q = head2, *cur = dummyHead;
        while (p != nullptr && q != nullptr)
        {
            if (p->val <= q->val)
            {
                cur->next = p;
                p = p->next;
                cur = cur->next;
            }
            else
            {
                cur->next = q;
                q = q->next;
                cur = cur->next;
            }
        }
        cur->next = p != nullptr ? p : q;
        ListNode *res = dummyHead->next;
        delete dummyHead;
        dummyHead = nullptr;

        return res;
    }

    void Test()
    {
        testVector = vector<int>(10000);
        int i = 0;
        for (auto &elem : testVector)
            elem = i++;
        testVector[0] = 10000;

        clock_t startTime = clock();
        HeapSort(testVector);
        // cout << testVector << endl;
        cout << (clock() - startTime) << "ms" << endl;

        ListNode *n1 = new ListNode(1);
        ListNode *n2 = new ListNode(2);
        ListNode *n3 = new ListNode(3);
        ListNode *n4 = new ListNode(4);
        n1->next = n2;
        n2->next = n3;
        n3->next = n4;

        // cout << n1 << endl;
        // DeleteNode(n1, n2);
        // DeleteNode(n1, n4);
        // DeleteNode(n1, n1);
        // cout << n1 << endl;

        // OddBeforeEven(testVector);
        // cout << testVector << endl;

        ListNode *res = GetNodeFromTail(n1, 1);
        cout << res << endl;
        res = GetNodeFromTail(n1, 3);
        cout << res << endl;
        // res = GetNodeFromTail(n1, 10);
        // cout << res << endl;

        ListNode *n5 = new ListNode(2);
        ListNode *n6 = new ListNode(4);
        ListNode *n7 = new ListNode(6);
        n5->next = n6;
        n6->next = n7;
        res = MergeLinkedList(n1, n5);
        cout << res << endl;
    }
}

namespace _09
{
    // 1. 快速排序
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int val = v[pos];
        sr = l - 1, br = r + 1;
        int i = l;
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[sr++ + 1]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[br-- - 1]);
        }
    }
    void QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int pos = l + (rand() % (r - l + 1));
        int sr = 0, br = 0;
        Partition(v, l, r, sr, br, pos);
        QuickSort_Process(v, l, sr);
        QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        QuickSort_Process(v, 0, v.size() - 1);
    }

    // 2. 归并排序
    void Merge(vector<int> &v, int l, int r, int mid)
    {
        vector<int> temp;
        int i = l, j = mid + 1;
        while (i <= mid && j <= r)
        {
            if (v[i] <= v[j])
                temp.push_back(v[i++]);
            else
                temp.push_back(v[j++]);
        }
        while (i <= mid)
            temp.push_back(v[i++]);
        while (j <= r)
            temp.push_back(v[j++]);
        ::copy(temp.begin(), temp.end(), v.begin() + l);
    }
    void MergeSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int mid = l + ((r - l) >> 1);
        MergeSort_Process(v, l, mid);
        MergeSort_Process(v, mid + 1, r);
        Merge(v, l, r, mid);
    }
    void MergeSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        MergeSort_Process(v, 0, v.size() - 1);
    }

    // 3. 冒泡排序
    void BubbleSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        for (int i = v.size() - 1; i > 0; i--)
        {
            for (int j = 0; j < i; j++)
            {
                if (v[j] > v[j + 1])
                    Swap(v[j], v[j + 1]);
            }
        }
    }

    // 4. 选择排序
    void SelectSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        int len = v.size();
        for (int i = 0; i < len; i++)
        {
            int minIndex = i;
            for (int j = i + 1; j < len; j++)
                minIndex = (v[minIndex] > v[j]) ? j : minIndex;
            Swap(v[minIndex], v[i]);
        }
    }

    // 5. 二分查找
    int BinarySearch(vector<int> &v, int tar)
    {
        if (v.size() == 0)
            return -1;
        int left = 0, right = v.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = left + ((right - left) >> 1);
            if (v[mid] < tar)
                left = mid + 1;
            else if (v[mid] > tar)
                right = mid - 1;
            else
                return mid;
        }
        return -1;
    }

    void Test()
    {
        SelectSort(testVector);
        cout << testVector << endl;

        cout << BinarySearch(testVector, 4) << endl;
    }
}

namespace _10
{
    // 1. 冒泡排序  O(n^2) | O(1)
    void BubbleSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        for (int i = v.size() - 1; i > 0; i--)
        {
            for (int j = 0; j < i; j++)
            {
                if (v[j] > v[j + 1])
                    Swap(v[j], v[j + 1]);
            }
        }
    }

    // 2. 插入排序  O(n^2) | O(1)
    void InsertSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        int len = v.size();
        for (int i = 1; i < len; i++)
        {
            for (int j = i; j > 0 && v[j] < v[j - 1]; j--)
                Swap(v[j], v[j - 1]);
        }
    }

    // 3. 归并排序  O(nlog(n)) | O(n)
    void Merge(vector<int> &v, int l, int r, int mid)
    {
        int i = l, j = mid + 1;
        vector<int> temp(r - l + 1);
        int k = 0;
        while (i <= mid && j <= r)
        {
            if (v[i] <= v[j])
                temp[k++] = v[i++];
            else
                temp[k++] = v[j++];
        }
        while (i <= mid)
            temp[k++] = v[i++];
        while (j <= r)
            temp[k++] = v[j++];
        ::copy(temp.begin(), temp.end(), v.begin() + l);
    }
    void _MergeSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int mid = l + ((r - l) >> 1);
        _MergeSort_Process(v, l, mid);
        _MergeSort_Process(v, mid + 1, r);
        Merge(v, l, r, mid);
    }
    void MergeSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _MergeSort_Process(v, 0, v.size() - 1);
    }

    // 4. 快速排序  O(nlog(n)) | O(log(n))
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int val = v[pos];
        sr = l - 1, br = r + 1;
        int i = l;
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[sr++ + 1]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[br-- - 1]);
        }
    }
    void _QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int pos = l + (rand() % (r - l + 1));
        int sr = 0, br = 0;
        Partition(v, l, r, sr, br, pos);
        _QuickSort_Process(v, l, sr);
        _QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        srand((unsigned int)time(NULL));
        _QuickSort_Process(v, 0, v.size() - 1);
    }

    // 5. 堆排序    O(nlog(n)) | O(1)
    void Heapify(vector<int> &v, int heapSize, int i = 0)
    {
        int left = i * 2 + 1, right = left + 1;
        while (left < heapSize)
        {
            int maxIndex = (right < heapSize && v[right] > v[left]) ? right : left;
            maxIndex = (v[i] > v[maxIndex]) ? i : maxIndex;
            if (maxIndex == i)
                return;
            Swap(v[maxIndex], v[i]);
            i = maxIndex;
            left = 2 * i + 1;
            right = left + 1;
        }
    }
    void HeapSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;

        int heapSize = v.size();
        for (int i = v.size() - 1; i >= 0; i--)
            Heapify(v, heapSize, i);

        while (heapSize > 0)
        {
            Swap(v[0], v[--heapSize]);
            Heapify(v, heapSize);
        }
    }

    // 6. 二分查找
    int BinarySearch(const vector<int> &v, int tar)
    {
        if (v.size() == 0)
            return -1;
        int left = 0, right = v.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = left + ((right - left) >> 1);
            if (v[mid] < tar)
                left = mid + 1;
            else if (v[mid] > tar)
                right = v[right] - 1;
            else
                return mid;
        }
        return -1;
    }

    // 7. 二叉树的镜像
    void Mirror(BiTreeNode *root)
    {
        if (root == nullptr)
            return;
        BiTreeNode *temp = root->lchild;
        root->lchild = root->rchild;
        root->rchild = temp;
        Mirror(root->lchild);
        Mirror(root->rchild);
    }

    // 8. 翻转链表
    ListNode *ReverseListNode(ListNode *head)
    {
        if (head == nullptr)
            return nullptr;
        ListNode *pPre = head, *pCur = head->next, *pNext;
        pPre->next = nullptr;
        while (pCur != nullptr)
        {
            pNext = pCur->next;
            pCur->next = pPre;
            pPre = pCur;
            pCur = pNext;
        }
        return pPre;
    }

    // 9. 删除链表结点  O(1)
    void DeleteNode(ListNode *&head, ListNode *&tar)
    {
        if (head == nullptr || tar == nullptr)
            return;

        // 尾结点
        if (tar->next == nullptr)
        {
            if (head->next == nullptr)
            {
                delete head;
                head = nullptr;
                return;
            }
            ListNode *p = head;
            while (p != nullptr && p->next != tar)
                p = p->next;
            if (p == nullptr)
                throw new logic_error("head doesn't contain target");
            delete tar;
            tar = nullptr;
            p->next = nullptr;
        }
        // 非尾结点
        else
        {
            ListNode *pNext = tar->next;
            tar->val = pNext->val;
            tar->next = pNext->next;
            delete pNext;
            pNext = nullptr;
        }
    }

    void Test()
    {
        // BubbleSort(testVector);
        // InsertSort(testVector);
        // MergeSort(testVector);
        // QuickSort(testVector);
        HeapSort(testVector);
        cout << testVector << endl;

        cout << BinarySearch(testVector, 6) << endl;

        BiTreeNode r1(1);
        BiTreeNode r2(2);
        BiTreeNode r3(3);
        BiTreeNode r4(4);
        BiTreeNode r5(5);
        r1.lchild = &r2;
        r1.rchild = &r3;
        r2.lchild = &r4;
        r2.rchild = &r5;

        Mirror(&r1);

        ListNode *n1 = new ListNode(1);
        ListNode *n2 = new ListNode(2);
        ListNode *n3 = new ListNode(3);
        ListNode *n4 = new ListNode(4);
        n1->next = n2;
        n2->next = n3;
        n3->next = n4;

        // ListNode* res = ReverseListNode(&n1);
        // cout << res << endl;

        cout << n1 << endl;
        // DeleteNode(n1, n1);
        // DeleteNode(n1, n2);
        DeleteNode(n1, n4);
        cout << n1 << endl;
    }
}

namespace _11
{
    // 1. 快速排序
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int val = v[pos];
        sr = l - 1, br = r + 1;
        int i = l;
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[sr++ + 1]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[br-- - 1]);
        }
    }
    void _QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int pos = l + (rand() % (r - l + 1));
        int sr = 0, br = 0;
        Partition(v, l, r, sr, br, pos);
        _QuickSort_Process(v, l, sr);
        _QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        srand((unsigned int)time(NULL));
        _QuickSort_Process(v, 0, v.size() - 1);
    }

    // 2. 计数排序 & 基数排序
    void _CountSort(vector<int> &v, int maxNum)
    {

        int *help = new int[maxNum + 1];
        memset(help, 0, sizeof(int) * (maxNum + 1));

        for (int i = 0; i < (int)v.size(); i++)
            help[v[i]]++;

        int k = 0;
        for (int i = 0; i < (maxNum + 1); i++)
        {
            for (int j = help[i]; j > 0; j--)
                v[k++] = i;
        }

        delete[] help;
        help = nullptr;
    }
    void CountSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _CountSort(v, *(::max_element(v.begin(), v.end())));
    }

    int GetMaxDigit(vector<int> &v)
    {
        int maxNum = *(::max_element(v.begin(), v.end()));
        int digit = 0;
        while (maxNum != 0)
        {
            digit++;
            maxNum /= 10;
        }
        return digit;
    }
    int GetDigit(int num, int d)
    {
        if (d <= 0)
            throw new logic_error("d is inavailable");
        int count = 0;
        int res = 0;
        while (count < d)
        {
            res = num % 10;
            count++;
            num /= 10;
        }
        return res;
    }
    void RadixSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;

        int maxDigit = GetMaxDigit(v);
        vector<queue<int>> buckets(10, queue<int>());

        int curDigit = 0;
        for (int i = 0; i < maxDigit; i++)
        {
            for (int j = 0; j < (int)v.size(); j++)
            {
                curDigit = GetDigit(v[j], i + 1);
                buckets[curDigit].push(v[j]);
            }

            int k = 0;
            for (int j = 0; j < 10; j++)
            {
                while (!buckets[j].empty())
                {
                    v[k++] = buckets[j].front();
                    buckets[j].pop();
                }
            }
        }
    }

    // 3. 浮点数二分查找
    bool BinarySearch(double l, double r, double tar, double precision = 1e-4)
    {
        double mid;
        while (r - l >= precision)
        {
            mid = l + (r - l) / 2;
            if (fabs(mid - tar) < precision)
                return true;
            else if (mid < tar)
                l = mid;
            else
                r = mid;
        }
        return false;
    }

    // 4. 两个栈实现队列
    template <class T>
    class MyQueue
    {
    private:
        stack<T> s1;
        stack<T> s2;

    public:
        void Push(const T &val)
        {
            while (!s2.empty())
            {
                s1.push(s2.top());
                s2.pop();
            }
            s1.push(val);
            while (!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }

        T Pop()
        {
            if (IsEmpty())
                throw new logic_error("queue is empty");
            T res = s2.top();
            s2.pop();
            return res;
        }

        bool IsEmpty()
        {
            return s2.empty();
        }

        T Front()
        {
            if (IsEmpty())
                throw new logic_error("queue is empty");
            return s2.top();
        }
    };

    // 5. 队列实现栈
    template <class T>
    class MyStack
    {
    private:
        queue<T> q;

    public:
        void Push(const T &val)
        {
            int len = q.size();
            q.push(val);
            for (int i = 0; i < len; i++)
            {
                q.push(q.front());
                q.pop();
            }
        }

        T Pop()
        {
            if (IsEmpty())
                throw new logic_error("stack is empty");
            T res = q.front();
            q.pop();
            return res;
        }

        bool IsEmpty()
        {
            return q.empty();
        }

        T Top()
        {
            if (IsEmpty())
                throw new logic_error("stack is empty");
            return q.front();
        }
    };

    // 6. 数组中重复数字
    bool GetSameElem(const vector<int> &v, int &res) // O(n) | O(n)
    {
        unordered_set<int> help;
        for (const auto elem : v)
        {
            if (help.count(elem) == 0)
                help.insert(elem);
            else
            {
                res = elem;
                return true;
            }
        }
        return false;
    }
    bool GetSameElem(vector<int> &v, int &res) // O(n) | O(1)
    {
        if (v.size() == 0)
            return false;

        for (const auto elem : v)
        {
            if (elem < 0 || elem > v.size() - 1)
                return false;
        }

        for (int i = 0; i < (int)v.size(); i++)
        {
            while (v[i] != i)
            {
                if (v[i] == v[v[i]])
                {
                    res = v[i];
                    return true;
                }

                Swap(v[i], v[v[i]]);
            }
        }

        return false;
    }

    // 7. 二叉树的递归遍历
    template <typename _Func>
    void PreOrder(BiTreeNode *root, _Func action)
    {
        if (root == nullptr)
            return;
        action(root->val);
        PreOrder(root->lchild, action);
        PreOrder(root->rchild, action);
    }

    template <typename _Func>
    void InOrder(BiTreeNode *root, _Func action)
    {
        if (root == nullptr)
            return;
        InOrder(root->lchild, action);
        action(root->val);
        InOrder(root->rchild, action);
    }

    template <typename _Func>
    void PostOrder(BiTreeNode *root, _Func action)
    {
        if (root == nullptr)
            return;
        PostOrder(root->lchild, action);
        PostOrder(root->rchild, action);
        action(root->val);
    }

    // 8. 二叉树的非递归遍历
    template <typename _Func>
    void InOrder_NonRecursive(BiTreeNode *root, _Func action)
    {
        stack<BiTreeNode *> s;
        while (root != nullptr || !s.empty())
        {
            if (root != nullptr)
            {
                s.push(root);
                root = root->lchild;
            }
            else
            {
                root = s.top();
                s.pop();
                action(root->val);
                root = root->rchild;
            }
        }
    }

    template <typename _Func>
    void PreOrder_NonRecursive(BiTreeNode *root, _Func action)
    {
        if (root == nullptr)
            return;
        stack<BiTreeNode *> s;
        s.push(root);
        BiTreeNode *cur;
        while (!s.empty())
        {
            cur = s.top();
            s.pop();
            action(cur->val);
            if (cur->rchild)
                s.push(cur->rchild);
            if (cur->lchild)
                s.push(cur->lchild);
        }
    }

    template <typename _Func>
    void PostOrder_NonRecursive(BiTreeNode *root, _Func action)
    {
        if (root == nullptr)
            return;
        stack<BiTreeNode *> s1, s2;
        s1.push(root);
        BiTreeNode *cur = root;
        while (!s1.empty())
        {
            cur = s1.top();
            s1.pop();
            s2.push(cur);
            if (cur->lchild)
                s1.push(cur->lchild);
            if (cur->rchild)
                s1.push(cur->rchild);
        }
        while (!s2.empty())
        {
            cur = s2.top();
            s2.pop();
            action(cur->val);
        }
    }

    // 9. 树的子结构
    bool DoesTree1HasTree2(BiTreeNode *root1, BiTreeNode *root2)
    {
        if (root2 == nullptr)
            return true;
        if (root1 == nullptr)
            return false;
        if (root1->val != root2->val)
            return false;
        return DoesTree1HasTree2(root1->lchild, root2->lchild) && DoesTree1HasTree2(root1->rchild, root2->rchild);
    }
    bool IsChild(BiTreeNode *root1, BiTreeNode *root2)
    {
        bool res = false;
        if (root1 != nullptr && root2 != nullptr)
        {
            if (root1->val == root2->val)
                res = DoesTree1HasTree2(root1, root2);
            if (!res)
                res = IsChild(root1->lchild, root2);
            if (!res)
                res = IsChild(root1->rchild, root2);
        }
        return res;
    }

    // 10. 对称二叉树
    bool IsSymmetrical(BiTreeNode *root1, BiTreeNode *root2)
    {
        if (root1 == nullptr && root2 == nullptr)
            return true;
        else if (root1 == nullptr || root2 == nullptr)
            return false;

        if (root1->val != root2->val)
            return false;

        return IsSymmetrical(root1->lchild, root2->rchild) && IsSymmetrical(root1->rchild, root2->lchild);
    }
    bool IsSymmetrical(BiTreeNode *root)
    {
        return IsSymmetrical(root, root);
    }

    void Test()
    {
        testVector = vector<int>(10000);
        for (int i = 0; i < 10000; i++)
            testVector[i] = 10000 - i;

        clock_t startTime = clock();
        RadixSort(testVector);
        // cout << testVector << endl;
        cout << (clock() - startTime) << "ms" << endl;

        cout << BinarySearch(1.0f, 100.0f, 114.0f) << endl;

        cout << endl;
        MyQueue<int> q;
        q.Push(1);
        q.Push(2);
        q.Push(3);
        q.Push(4);
        cout << q.Pop() << endl;
        cout << q.Pop() << endl;
        cout << q.IsEmpty() << endl;
        cout << q.Front() << endl;

        cout << endl;
        MyStack<int> s;
        s.Push(1);
        s.Push(2);
        s.Push(3);
        s.Push(4);
        cout << s.Pop() << endl;
        cout << s.Pop() << endl;
        cout << (s.IsEmpty() ? "TRUE" : "FALSE") << endl;
        cout << s.Top() << endl;

        cout << endl;
        testVector = vector<int>{1, 4, 2, 3, 4, 2};
        int res = 0;
        GetSameElem(testVector, res);
        cout << res << endl;

        BiTreeNode r1(1);
        BiTreeNode r2(2);
        BiTreeNode r3(2);
        BiTreeNode r4(3);
        BiTreeNode r5(3);
        r1.lchild = &r2;
        r1.rchild = &r3;
        r2.rchild = &r4;
        r3.lchild = &r5;

        auto printFunc = [](int val) -> void
        {
            cout << val << " ";
        };

        PreOrder(&r1, printFunc);
        cout << endl;
        cout << endl;
        InOrder(&r1, printFunc);
        cout << endl;
        cout << endl;
        PostOrder(&r1, printFunc);
        cout << endl;
        cout << endl;
        InOrder_NonRecursive(&r1, printFunc);
        cout << endl;
        cout << endl;
        PreOrder_NonRecursive(&r1, printFunc);
        cout << endl;
        cout << endl;
        PostOrder_NonRecursive(&r1, printFunc);

        cout << endl;
        cout << endl;
        cout << IsSymmetrical(&r1) << endl;

        cout << IsChild(&r1, &r4) << endl;
    }
}

namespace _12
{
    // 1. 快速排序
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int val = v[pos];
        sr = l - 1, br = r + 1;
        int i = l;
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[++sr]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[--br]);
        }
    }
    void QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int pos = l + (rand() % (r - l + 1));
        int sr = 0, br = 0;
        Partition(v, l, r, sr, br, pos);
        QuickSort_Process(v, l, sr);
        QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        QuickSort_Process(v, 0, v.size() - 1);
    }

    // 2. 归并排序
    void Merge(vector<int> &v, int l, int r, int mid)
    {
        int i = l, j = mid + 1;
        vector<int> temp(r - l + 1);
        int k = 0;
        while (i <= mid && j <= r)
        {
            if (v[i] <= v[j])
                temp[k++] = v[i++];
            else
                temp[k++] = v[j++];
        }
        while (i <= mid)
            temp[k++] = v[i++];
        while (j <= r)
            temp[k++] = v[j++];
        ::copy(temp.begin(), temp.end(), v.begin() + l);
    }
    void MergeSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int mid = l + ((r - l) >> 1);
        MergeSort_Process(v, l, mid);
        MergeSort_Process(v, mid + 1, r);
        Merge(v, l, r, mid);
    }
    void MergeSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        MergeSort_Process(v, 0, v.size() - 1);
    }

    // 3. 堆排序
    void Heapify(vector<int> &v, int heapSize, int i)
    {
        int left = 2 * i + 1, right = left + 1;
        while (left < heapSize)
        {
            int maxIndex = (right < heapSize && v[right] > v[left]) ? right : left;
            maxIndex = (v[i] > v[maxIndex]) ? i : maxIndex;
            if (maxIndex == i)
                return;
            Swap(v[maxIndex], v[i]);
            i = maxIndex;
            left = 2 * i + 1;
            right = left + 1;
        }
    }
    void HeapSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        int heapSize = v.size();
        for (int i = heapSize - 1; i >= 0; --i)
            Heapify(v, heapSize, i);
        while (heapSize > 0)
        {
            Swap(v[0], v[--heapSize]);
            Heapify(v, heapSize, 0);
        }
    }

    // 4. 二叉树的非递归遍历
    template <typename _Action>
    void PreOrder(BiTreeNode *root, _Action action)
    {
        if (root == nullptr)
            return;
        stack<BiTreeNode *> s;
        s.push(root);
        BiTreeNode *cur;
        while (!s.empty())
        {
            cur = s.top();
            s.pop();
            action(cur->val);
            if (cur->rchild)
                s.push(cur->rchild);
            if (cur->lchild)
                s.push(cur->lchild);
        }
    }
    template <typename _Action>
    void PostOrder(BiTreeNode *root, _Action action)
    {
        if (root == nullptr)
            return;
        stack<BiTreeNode *> s1;
        stack<BiTreeNode *> s2;
        s1.push(root);
        BiTreeNode *cur;
        while (!s1.empty())
        {
            cur = s1.top();
            s1.pop();
            s2.push(cur);
            if (cur->lchild)
                s1.push(cur->lchild);
            if (cur->rchild)
                s1.push(cur->rchild);
        }
        while (!s2.empty())
        {
            cur = s2.top();
            s2.pop();
            action(cur->val);
        }
    }
    template <typename _Action>
    void InOrder(BiTreeNode *root, _Action action)
    {
        stack<BiTreeNode *> s;
        while (root != nullptr || !s.empty())
        {
            if (root != nullptr)
            {
                s.push(root);
                root = root->lchild;
            }
            else
            {
                root = s.top();
                s.pop();
                action(root->val);
                root = root->rchild;
            }
        }
    }

    // 5. 树的子结构
    bool DoesTree1HasTree2(BiTreeNode *root1, BiTreeNode *root2)
    {
        if (root2 == nullptr)
            return true;
        if (root1 == nullptr)
            return false;
        if (root1->val != root2->val)
            return false;
        return DoesTree1HasTree2(root1->lchild, root2->lchild) &&
               DoesTree1HasTree2(root1->rchild, root2->rchild);
    }
    bool IsSubTree(BiTreeNode *root1, BiTreeNode *root2)
    {
        if (root1 == nullptr || root2 == nullptr)
            return false;
        bool res = false;
        if (root1->val == root2->val)
            res = DoesTree1HasTree2(root1, root2);
        if (!res)
            res = IsSubTree(root1->lchild, root2);
        if (!res)
            res = IsSubTree(root1->rchild, root2);

        return res;
    }

    // 6. 翻转链表
    ListNode *ReverseList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *pPre = head, *pCur = head->next, *pNext;
        pPre->next = nullptr;
        while (pCur != nullptr)
        {
            pNext = pCur->next;
            pCur->next = pPre;
            pPre = pCur;
            pCur = pNext;
        }
        return pPre;
    }

    // 7. 合并两个已排序链表
    ListNode *MergeList(ListNode *head1, ListNode *head2)
    {
        ListNode dummyHead(0);
        ListNode *p = head1, *q = head2, *cur = &dummyHead;
        while (p != nullptr && q != nullptr)
        {
            if (p->val <= q->val)
            {
                cur->next = p;
                p = p->next;
            }
            else
            {
                cur->next = q;
                q = q->next;
            }
            cur = cur->next;
        }
        if (p != nullptr)
            cur->next = p;
        if (q != nullptr)
            cur->next = q;
        return dummyHead.next;
    }

    // 8. 斐波那契数列
    int Fib(int n)
    {
        if (n <= 0)
            return 0;
        else if (n == 1 || n == 2)
            return 1;
        int minusOne = 1;
        int minusTwo = 1;
        int cur = 0;
        for (int i = 3; i <= n; i++)
        {
            cur = minusOne + minusTwo;
            minusTwo = minusOne;
            minusOne = cur;
        }
        return cur;
    }

    // 9. 二维数组查找
    bool MatrixSearch(const vector<vector<int>> &matrix, int tar)
    {
        if (matrix.size() == 0 || matrix[0].size() == 0)
            return false;
        int row = matrix.size(), col = matrix[0].size();
        int i = 0, j = col - 1;
        while (i < row && j >= 0)
        {
            if (matrix[i][j] < tar)
                ++i;
            else if (matrix[i][j] > tar)
                --j;
            else
                return true;
        }
        return false;
    }

    void Test()
    {
        HeapSort(testVector);
        cout << testVector << endl;

        BiTreeNode r1(1);
        BiTreeNode r2(2);
        BiTreeNode r3(3);
        BiTreeNode r4(4);
        BiTreeNode r5(5);
        r1.lchild = &r2;
        r1.rchild = &r3;
        r2.lchild = &r4;
        r2.rchild = &r5;

        PreOrder(&r1, [](int val) -> void
                 { cout << val << endl; });
        cout << endl;
        PostOrder(&r1, [](int val) -> void
                  { cout << val << endl; });
        cout << endl;
        InOrder(&r1, [](int val) -> void
                { cout << val << endl; });

        cout << endl;
        cout << IsSubTree(&r1, &r2) << endl;

        ListNode n1(1);
        ListNode n2(2);
        ListNode n3(3);
        ListNode n4(4);
        n1.next = &n2;
        n2.next = &n3;
        n3.next = &n4;

        // ListNode* res = ReverseList(&n1);
        // cout << res << endl;

        ListNode n5(2);
        ListNode n6(6);
        n5.next = &n6;

        ListNode *res = MergeList(&n1, &n5);
        cout << res << endl;

        cout << Fib(10) << endl;

        vector<vector<int>> matrix{
            {1, 2, 3, 4, 5},
            {2, 3, 5, 6, 8},
            {3, 4, 6, 7, 10},
        };
        cout << MatrixSearch(matrix, 4) << endl;
        cout << MatrixSearch(matrix, 9) << endl;
    }
}

namespace _13
{
    // 1. 快速排序
    void Partition(vector<int> &v, int l, int r, int &sr, int &br, int pos)
    {
        int val = v[pos];
        sr = l - 1, br = r + 1;
        int i = l;
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[++sr]);
            else if (v[i] == val)
                i++;
            else
                Swap(v[i], v[--br]);
        }
    }
    void _QuickSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int pos = l + (rand() % (r - l + 1));
        int sr = 0, br = 0;
        Partition(v, l, r, sr, br, pos);
        _QuickSort_Process(v, l, sr);
        _QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        srand((unsigned int)time(NULL));
        _QuickSort_Process(v, 0, v.size() - 1);
    }

    // 2. 归并排序
    void Merge(vector<int> &v, int l, int r, int mid)
    {
        int i = l, j = mid + 1;
        vector<int> temp(r - l + 1);
        int k = 0;
        while (i <= mid && j <= r)
        {
            if (v[i] <= v[j])
                temp[k++] = v[i++];
            else
                temp[k++] = v[j++];
        }
        while (i <= mid)
            temp[k++] = v[i++];
        while (j <= r)
            temp[k++] = v[j++];
        ::copy(temp.begin(), temp.end(), v.begin() + l);
    }
    void _MergeSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int mid = l + ((r - l) >> 1);
        _MergeSort_Process(v, l, mid);
        _MergeSort_Process(v, mid + 1, r);
        Merge(v, l, r, mid);
    }
    void MergeSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _MergeSort_Process(v, 0, v.size() - 1);
    }

    // 3. 包含min函数的栈
    template <class T>
    class MinStack
    {
    private:
        stack<T> m_data;
        stack<T> m_help;

        void InvalidCheck()
        {
            if (m_data.empty())
                throw new logic_error("stack is empty");
        }

    public:
        void Push(const T &val)
        {
            m_data.push(val);
            if (m_help.empty() || val < m_help.top())
                m_help.push(val);
            else
                m_help.push(m_help.top());
        }

        void Pop()
        {
            InvalidCheck();

            m_data.pop();
            m_help.pop();
        }

        T top()
        {
            InvalidCheck();

            return m_data.top();
        }

        T Min()
        {
            InvalidCheck();

            return m_help.top();
        }
    };

    // 4. 两个栈实现队列
    template <class T>
    class MyQueue
    {
    private:
        stack<int> s1;
        stack<int> s2;

        void InvalidCheck()
        {
            if (s1.empty())
                throw new logic_error("queue is empty");
        }

    public:
        void Push(const T &val)
        {
            while (!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
            s2.push(val);
            while (!s2.empty())
            {
                s1.push(s2.top());
                s2.pop();
            }
        }

        T Pop()
        {
            InvalidCheck();

            T res = s1.top();
            s1.pop();
            return res;
        }

        T Top()
        {
            InvalidCheck();

            return s1.top();
        }
    };

    // 5. 队列实现栈
    template <class T>
    class MyStack
    {
    private:
        queue<T> q;

    public:
        void Push(const T &val)
        {
            int count = q.size();
            q.push(val);
            for (int i = 0; i < count; ++i)
            {
                q.push(q.front());
                q.pop();
            }
        }

        T Pop()
        {
            if (q.empty())
                throw new logic_error("stack is empty");

            T res = q.front();
            q.pop();
            return res;
        }
    };

    // 6. 从上向下分行打印二叉树
    void PrintBiTree(BiTreeNode *root)
    {
        if (root == nullptr)
            return;
        queue<BiTreeNode *> q;
        q.push(root);
        int nextLevel = 0;
        int toBePrint = 1;
        BiTreeNode *cur;
        while (!q.empty())
        {
            cur = q.front();
            q.pop();
            cout << cur->val << " ";
            --toBePrint;

            if (cur->lchild)
            {
                q.push(cur->lchild);
                ++nextLevel;
            }
            if (cur->rchild)
            {
                q.push(cur->rchild);
                ++nextLevel;
            }

            if (toBePrint == 0)
            {
                cout << '\n';
                toBePrint = nextLevel;
                nextLevel = 0;
            }
        }
    }

    // 7. 二叉树的镜像
    void Mirror(BiTreeNode *root)
    {
        if (root == nullptr)
            return;
        BiTreeNode *temp = root->lchild;
        root->lchild = root->rchild;
        root->rchild = temp;

        Mirror(root->lchild);
        Mirror(root->rchild);
    }

    // 8. 数组中重复的数字
    int GetSameNum(vector<int> &v)
    {
        if (v.size() == 0)
            return -1;
        for (int i = 0; i < v.size(); ++i)
        {
            while (v[i] != i)
            {
                if (v[i] == v[v[i]])
                    return v[i];
                Swap(v[i], v[v[i]]);
            }
        }
        return -1;
    }

    // 9. 机器人的运动范围
    int SumDigit(int num)
    {
        int sum = 0;
        while (num != 0)
        {
            sum += (num % 10);
            num /= 10;
        }
        return sum;
    }
    int RobotMoveRange(int row, int col, int i, int j,
                       int k, vector<vector<bool>> &record)
    {
        if (i < 0 || i >= row || j < 0 || j >= col || record[i][j] ||
            (SumDigit(i) + SumDigit(j)) > k)
        {
            return 0;
        }

        record[i][j] = true;
        return 1 + RobotMoveRange(row, col, i - 1, j, k, record) +
               RobotMoveRange(row, col, i + 1, j, k, record) +
               RobotMoveRange(row, col, i, j - 1, k, record) +
               RobotMoveRange(row, col, i, j + 1, k, record);
    }
    int RobotMoveRange(int row, int col, int k)
    {
        if (row <= 0 || col <= 0)
            return 0;
        vector<vector<bool>> record(row, vector<bool>(col, false));
        return RobotMoveRange(row, col, 0, 0, k, record);
    }

    // 10. 倒数第k个链表结点
    ListNode *GetListNode(ListNode *head, int k)
    {
        if (head == nullptr)
            return nullptr;
        if (k <= 0)
            throw new logic_error("k cannot be zero or negative number");
        ListNode *fast = head, *slow = head;
        int count = 0;
        while (fast != nullptr && count < k)
        {
            fast = fast->next;
            count++;
        }
        if (fast == nullptr && count < k)
            throw new logic_error("k is larger than node count");
        while (fast != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }

    void Test()
    {
        MergeSort(testVector);
        cout << testVector << endl;

        MinStack<int> ms;
        ms.Push(3);
        ms.Push(2);
        ms.Push(1);
        ms.Push(5);
        cout << "cur min = " << ms.Min() << endl;
        ms.Pop();
        ms.Pop();
        cout << "cur min = " << ms.Min() << endl;

        MyQueue<int> mq;
        mq.Push(1);
        mq.Push(2);
        mq.Push(3);
        mq.Push(4);
        cout << mq.Pop() << endl;
        cout << mq.Pop() << endl;

        MyStack<int> s;
        s.Push(1);
        s.Push(2);
        s.Push(3);
        s.Push(4);
        s.Push(5);
        cout << s.Pop() << endl;
        cout << s.Pop() << endl;
        cout << s.Pop() << endl;

        cout << endl;
        BiTreeNode r1(1);
        BiTreeNode r2(2);
        BiTreeNode r3(3);
        BiTreeNode r4(4);
        BiTreeNode r5(5);
        r1.lchild = &r2;
        r1.rchild = &r3;
        r2.lchild = &r4;
        r2.rchild = &r5;

        Mirror(&r1);

        PrintBiTree(&r1);

        vector<int> v{1, 2, 4, 3, 2, 4};
        cout << GetSameNum(v) << endl;

        cout << RobotMoveRange(15, 15, 6) << endl;

        ListNode n1(1);
        ListNode n2(2);
        ListNode n3(3);
        ListNode n4(4);
        n1.next = &n2;
        n2.next = &n3;
        n3.next = &n4;

        cout << GetListNode(&n1, 4) << endl;
    }
}

namespace _14
{
    // 1. 归并排序
    void Merge(vector<int> &v, int l, int r, int mid)
    {
        int i = l, j = mid + 1;
        vector<int> temp(r - l + 1);
        int k = 0;
        while (i <= mid && j <= r)
        {
            if (v[i] <= v[j])
                temp[k++] = v[i++];
            else
                temp[k++] = v[j++];
        }
        while (i <= mid)
            temp[k++] = v[i++];
        while (j <= r)
            temp[k++] = v[j++];
        ::copy(temp.begin(), temp.end(), v.begin() + l);
    }
    void _MergeSort_Process(vector<int> &v, int l, int r)
    {
        if (l >= r)
            return;
        int mid = l + ((r - l) >> 1);
        _MergeSort_Process(v, l, mid);
        _MergeSort_Process(v, mid + 1, r);
        Merge(v, l, r, mid);
    }
    void MergeSort(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        _MergeSort_Process(v, 0, v.size() - 1);
    }

    // 2. 调整数组顺序使奇数在偶数前
    void OddBeforeEven(vector<int> &v)
    {
        if (v.size() <= 1)
            return;
        int oddRange = -1;
        for (int i = 0; i < (int)v.size(); ++i)
        {
            if ((v[i] & 0x1) == 1)
                Swap(v[i], v[++oddRange]);
        }
    }

    // 3. 删除链表结点
    ListNode *DeleteNode(ListNode *head, ListNode *tar)
    {
        if (head == nullptr || tar == nullptr)
            return nullptr;

        if (tar->next == nullptr)
        {
            ListNode *cur = head;
            while (cur->next != tar)
                cur = cur->next;
            cur->next = nullptr;
            delete tar;
            tar = nullptr;
        }
        else
        {
            ListNode *pNext = tar->next;
            tar->val = pNext->val;
            tar->next = pNext->next;
            delete pNext;
            pNext = nullptr;
        }

        return head;
    }

    // 4. 翻转链表
    ListNode *ReverseList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode *pPre = head, *pCur = head->next, *pNext;
        pPre->next = nullptr;
        while (pCur != nullptr)
        {
            pNext = pCur->next;
            pCur->next = pPre;
            pPre = pCur;
            pCur = pNext;
        }

        return pPre;
    }

    // 5. 从尾到头打印链表
    void ReversePrintList(const ListNode *head)
    {
        if (head == nullptr)
            return;
        ReversePrintList(head->next);
        cout << head->val << " ";
    }

    // 6. 替换空格
    void ReplaceSpace(string &str)
    {
        int spaceCount = ::count(str.begin(), str.end(), ' ');
        int originSize = str.size();
        int newSize = originSize + spaceCount * 2;
        str.resize(newSize);

        int i = originSize - 1, j = newSize - 1;
        while (i >= 0)
        {
            if (str[i] == ' ')
            {
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '%';
                --i;
            }
            else
                str[j--] = str[i--];
        }
    }

    // 7. 矩阵路径
    bool _MatrixPath_Process(const vector<vector<char>> &matrix, const string &str,
                             int i, int j, int &curPos, vector<vector<bool>> &record)
    {
        int row = matrix.size();
        int col = matrix[0].size();

        if (curPos == str.size())
            return true;

        bool hasPath = false;

        if (i >= 0 && i < row && j >= 0 && j < col && !record[i][j] && matrix[i][j] == str[curPos])
        {
            ++curPos;
            record[i][j] = true;
            hasPath = _MatrixPath_Process(matrix, str, i - 1, j, curPos, record) ||
                      _MatrixPath_Process(matrix, str, i + 1, j, curPos, record) ||
                      _MatrixPath_Process(matrix, str, i, j - 1, curPos, record) ||
                      _MatrixPath_Process(matrix, str, i, j + 1, curPos, record);
            if (!hasPath)
            {
                --curPos;
                record[i][j] = false;
            }
        }

        return hasPath;
    }
    bool MatrixPath(const vector<vector<char>> &matrix, const string &str)
    {
        if (matrix.size() == 0 || matrix[0].size() == 0)
            return false;
        vector<vector<bool>> record(matrix.size(),
                                    vector<bool>(matrix[0].size(), false));
        int curPos = 0;

        for (int i = 0; i < matrix.size(); ++i)
        {
            for (int j = 0; j < matrix[0].size(); ++j)
            {
                if (_MatrixPath_Process(matrix, str, i, j, curPos, record))
                    return true;
            }
        }

        return false;
    }

    // 8. 包含min函数的栈
    template <class T>
    class MinStack
    {
    private:
        stack<T> m_data;
        stack<T> m_help;

        void ExCheck()
        {
            if (m_data.empty())
                throw new logic_error("stack is empty");
        }

    public:
        void Push(const T &val)
        {
            m_data.push(val);
            if (m_help.empty() || val < m_help.top())
                m_help.push(val);
            else
                m_help.push(m_help.top());
        }

        void Pop()
        {
            ExCheck();

            m_data.pop();
            m_help.pop();
        }

        T Min()
        {
            ExCheck();

            return m_help.top();
        }

        T Top()
        {
            ExCheck();

            return m_data.top();
        }
    };

    // 9. 搜索二叉树的后序遍历
    bool _IsBSTPostOrder_Process(const vector<int> &v, int l, int r)
    {
        if (l >= r)
            return true;

        int i = l;
        for (; i < r && v[i] < v[r]; ++i)
            ;
        for (int j = i; j < r; ++j)
        {
            if (v[j] < v[r])
                return false;
        }

        bool left = true;
        if (i > 0)
            left = _IsBSTPostOrder_Process(v, l, i - 1);
        bool right = true;
        if (i < r - 1)
            right = _IsBSTPostOrder_Process(v, i, r - 1);
        return left && right;
    }
    bool IsBSTPostOrder(const vector<int> &v)
    {
        return _IsBSTPostOrder_Process(v, 0, v.size() - 1);
    }

    void Test()
    {
        MergeSort(testVector);
        cout << testVector << endl;

        OddBeforeEven(testVector);
        cout << testVector << endl;

        ListNode *n1 = new ListNode(1);
        ListNode *n2 = new ListNode(2);
        ListNode *n3 = new ListNode(3);
        ListNode *n4 = new ListNode(4);
        ListNode *n5 = new ListNode(5);
        n1->next = n2;
        n2->next = n3;
        n3->next = n4;
        n4->next = n5;

        DeleteNode(n1, n5);
        DeleteNode(n1, n2);
        cout << n1 << endl;

        ListNode *res = ReverseList(n1);
        cout << res << endl;

        ReversePrintList(res);

        cout << endl;
        string str("we are happy");
        ReplaceSpace(str);
        cout << str << endl;

        vector<vector<char>> matrix = {
            {'a', 'b', 't', 'g'},
            {'c', 'f', 'c', 's'},
            {'j', 'd', 'e', 'h'},
        };
        cout << MatrixPath(matrix, "bfce") << endl;

        MinStack<int> ms;
        ms.Push(5);
        ms.Push(4);
        ms.Push(3);
        ms.Push(4);
        ms.Push(6);
        ms.Pop();
        cout << "min = " << ms.Min() << endl;
        cout << "top = " << ms.Top() << endl;

        vector<int> v{1,3,5,8,6,4};
        cout << IsBSTPostOrder(v) << endl; 
    }
}

namespace _15
{
    // 1. 快速排序
    void Partition(vector<int>& v, int l, int r, int& sr, int& br, int pos)
    {
        int val = v[pos];
        sr = l - 1, br = r + 1;
        int i = l;
        while (i < br)
        {
            if (v[i] < val)
                Swap(v[i++], v[++sr]);
            else if (v[i] == val) 
                ++i;
            else
                Swap(v[i], v[--br]);
        }
    }
    void _QuickSort_Process(vector<int>& v, int l, int r)
    {
        if (l >= r)
            return;
        int pos = l + (rand() % (r - l + 1));
        int sr = 0, br = 0;
        Partition(v, l, r, sr, br, pos);
        _QuickSort_Process(v, l, sr);
        _QuickSort_Process(v, br, r);
    }
    void QuickSort(vector<int>& v)
    {
        if (v.size() <= 1)
            return;
        _QuickSort_Process(v, 0, v.size() - 1);
    }

    // 2. 对称的二叉树
    bool IsSymmetryTree(BiTreeNode* r1, BiTreeNode* r2)
    {
        if (r1 == nullptr && r2 == nullptr)
            return true;
        
        if (r1 == nullptr || r2 == nullptr)
            return false;

        if (r1->val != r2->val)
            return false;

        return IsSymmetryTree(r1->lchild, r2->rchild) && IsSymmetryTree(r1->rchild, r2->lchild);
    }
    bool IsSymmetryTree(BiTreeNode* root)
    {
        if (root == nullptr)
            return false;
        return IsSymmetryTree(root, root);
    }

    // 3. 之字形打印二叉树
    void PrintTree(BiTreeNode* root)
    {
        if (root == nullptr)
            return;
        stack<BiTreeNode*> s1;
        stack<BiTreeNode*> s2;
        s1.push(root);
        bool isL2R = true;
        BiTreeNode* cur;
        while (!s1.empty() || !s2.empty())
        {
            if (isL2R)
            {
                cur = s1.top();
                s1.pop();
                cout << cur->val << " ";
                if (cur->lchild)
                    s2.push(cur->lchild);
                if (cur->rchild)
                    s2.push(cur->rchild);
            }
            else
            {
                cur = s2.top();
                s2.pop();
                cout << cur->val << " ";
                if (cur->rchild)
                    s1.push(cur->rchild);
                if (cur->lchild)
                    s1.push(cur->lchild);
            }

            if (isL2R && s1.empty())
            {
                isL2R = false;
                cout << endl;
            }
            else if (!isL2R && s2.empty()) 
            {
                isL2R = true;
                cout << endl;
            }
        }
    }

    // 4. 复杂链表的复制
    RandListNode* CopyRandList(RandListNode* head)
    {
        if (head == nullptr)
            return nullptr;

        // 生成拷贝结点
        RandListNode* cur = head;
        while (cur != nullptr)
        {
            RandListNode* copyNode = new RandListNode(cur->val);
            copyNode->next = cur->next;
            cur->next = copyNode;
            cur = cur->next->next;
        }
        
        // 构建rand关系
        cur = head;
        while (cur != nullptr)
        {
            cur->next->rand = (cur->rand) ? cur->rand->next : nullptr; 
            cur = cur->next->next;
        }

        // 构建next关系
        cur = head;
        RandListNode* res = head->next;
        while (cur != nullptr)
        {
            RandListNode* temp = cur->next->next;
            RandListNode* pNext = cur->next;
            // 复原链表
            cur->next = pNext->next; 
            pNext->next = (pNext->next) ? pNext->next->next : nullptr;
            cur = temp;
        }

        return res;
    }

    // 5. 最小k个数
    vector<int> GetMinK(vector<int>& v, int k)
    {
        if (v.size() == 0 || k <= 0)
            return vector<int>();

        priority_queue<int> heep;
        int i = 0;
        for (; i < k; ++i)
            heep.push(v[i]);
        for (; i < (int)v.size(); ++i)
        {
            if (v[i] < heep.top())
            {
                heep.pop();
                heep.push(v[i]);
            }
        }

        vector<int> res(k);
        for (i = 0; i < k; ++i)
        {
            res[i] = heep.top();
            heep.pop();
        }

        return res;
    }

    // 6. 数组中超过一半的数
    int OutOfHalf(vector<int>& v)
    {
        int count = 1;
        int res = v[0];
        for (int i = 1; i < (int)v.size(); ++i)
        {
            if (count == 0)
            {
                res = v[i];
                count = 1;
            }
            else if (res == v[i])
                ++count;
            else
                --count;
        }

        return res;
    }

    void Test_01()
    {
        cout << "Please input the count of array: ";
        int count = 0;
        cin >> count;
        vector<int> v(count);
        cout << "Please input all the value of each element(use space to split each value): \n> " ;
        for (int i = 0; i < count; ++i)
        {
            int val = 0;
            cin >> val;
            v[i] = val;
        }
        QuickSort(v);
        cout << "sort result : " << endl << v << endl;
    }

    void Test_02()
    {
        BiTreeNode r1(1);
        BiTreeNode r2(2);
        BiTreeNode r3(3);
        BiTreeNode r4(4);
        BiTreeNode r5(5);
        r1.lchild = &r2;
        r1.rchild = &r3;
        r2.lchild = &r4;
        r3.rchild = &r5;

        cout << IsSymmetryTree(&r1) << endl;

        PrintTree(&r1);

        RandListNode n1(1);
        RandListNode n2(2);
        RandListNode n3(3);
        RandListNode n4(4);
        RandListNode n5(5);
        n1.next = &n2;
        n2.next = &n3;
        n3.next = &n4;
        n4.next = &n5;
        n1.rand = &n3;
        n2.rand = &n1;

        RandListNode* res = CopyRandList(&n1);

        vector<int> vRes = GetMinK(testVector, 4);
        cout << vRes << endl;

        vRes = {1,2,5,1,1,3,1};
        cout << OutOfHalf(vRes) << endl;
    }
}

namespace TestForExercise
{
    struct A
    {
        int num;
        double d;
        char arr[20];
    }; // 32

    struct B
    {
        char c;
        A a;
        int arr[3];
        float f;
        int *p;
    };

    struct C
    {
        A a;
        B b;
        A *p_a;
        B *p_b;
    };

    struct D
    {
        A a;
        int num;
        double d;
        char c;

        virtual void Func() = 0;
    };

    struct E : public A
    {
        int num;
        double dArr[2];
    };

    char *my_strcat(char *des, const char *src)
    {
        if (des == nullptr || src == nullptr)
            return nullptr;
        memcpy(des + strlen(des), src, strlen(src) + 1);
        return des;
    }

    void Test()
    {
        char str1[10] = "abc";
        cout << my_strcat(str1, "dddd") << endl;
    }
}

namespace TestForRValue
{
    void Process(int &a)
    {
        cout << "Process(int& a)" << a << endl;
    }

    void Process(int &&a)
    {
        cout << "Process(int&& a)" << a << endl;
    }

    class MyString
    {
    public:                  // 计数板块
        static size_t DCtor; // default ctor
        static size_t Ctor;  // ctor
        static size_t CCtor; // copy ctor
        static size_t MCtor; // move ctor
        static size_t CAsgn; // copy asign
        static size_t MAsgn; // move asign
        static size_t Dtor;  // dtor

    public:
        MyString() : m_len(0), m_base(nullptr) { ++DCtor; }

        MyString(const char *str)
        {
            m_len = strlen(str);
            _InitData(this->m_base, str, m_len);
            ++Ctor;
        }

        MyString(const MyString &str) : m_len(str.m_len)
        {
            _InitData(this->m_base, str.m_base, m_len);
            ++CCtor;
        }

        MyString &operator=(const MyString &str)
        {
            // 1. 自我赋值检测
            if (this == &str)
                return *this;
            // 2. 清空原数据
            if (m_base != nullptr)
                delete[] m_base;
            // 3. 拷贝数据
            m_base = new char[str.m_len + 1];
            memcpy(m_base, str.m_base, str.m_len);
            m_base[str.m_len] = '\0';

            ++CAsgn;

            return *this;
        }

        MyString(MyString &&str) noexcept
            : m_len(str.m_len), m_base(str.m_base)
        {
            str.m_len = 0;
            str.m_base = nullptr; // 右值指向断开
            ++MCtor;
        }

        MyString &operator=(MyString &&str) noexcept
        {
            if (this == &str)
                return *this;

            this->m_len = str.m_len;
            this->m_base = str.m_base;
            str.m_base = nullptr;
            str.m_len = 0;

            ++MAsgn;
            return *this;
        }

        virtual ~MyString()
        {
            if (m_base)
                delete[] m_base;
            ++Dtor;
        }

        bool operator<(const MyString &str) const
        {
            return (strcmp(this->m_base, str.m_base) < 0);
        }

        bool operator==(const MyString &str) const
        {
            return (strcmp(this->m_base, str.m_base) == 0);
        }

    private:
        char *m_base;
        size_t m_len;

    private:
        void _InitData(char *base, const char *src, int len)
        {
            base = new char[len + 1];
            memcpy(base, src, len);
            base[len] = '\0';
        }
    };
    size_t MyString::DCtor = 0;
    size_t MyString::Ctor = 0;
    size_t MyString::CCtor = 0;
    size_t MyString::MCtor = 0;
    size_t MyString::CAsgn = 0;
    size_t MyString::MAsgn = 0;
    size_t MyString::Dtor = 0;

    void Test()
    {
        char buf[10];

        cout << "vector : " << endl;
        vector<MyString> v;
        clock_t startTime = clock();
        for (long i = 0; i < 1000000; i++)
        {
            snprintf(buf, 10, "%d", rand());
            v.push_back(MyString(buf));
        }
        cout << (clock() - startTime) << "ms" << endl;
        cout << "CTOR = " << MyString::Ctor << endl;
        cout << "MCTOR = " << MyString::MCtor << endl;

        cout << endl;
        cout << "set : " << endl;
        set<MyString> s;
        startTime = clock();
        for (long i = 0; i < 1000000; i++)
        {
            snprintf(buf, 10, "%d", rand());
            s.insert(buf);
        }
        cout << (clock() - startTime) << "ms" << endl;
    }
}

namespace TestForOverride
{
    class Base
    {
    public:
        virtual void Func1() final
        {
            printf("%p\n", &Func1);
        }
        virtual void Func2()
        {
            printf("%p\n", &Func2);
        }
        virtual void Func3() = 0;
    };

    class Derived : public Base
    {
    public:
        void Func2(int a)
        {
            printf("%p\n", &Func2);
        }
        virtual void Func3() override
        {
            printf("%p\n", &Func3);
        }
    };

    void Test()
    {
        Derived d;
        d.Func1();
        d.Func2(1);
        d.Func3();
    }
}

namespace TestForSharedPtr
{
    template <class T>
    class MyAutoPtr
    {
    private:
        size_t *m_count;
        T *m_ptr;

    public:
        MyAutoPtr() : m_count(new size_t), m_ptr(nullptr) {}

        MyAutoPtr(T *ptr) : m_ptr(ptr)
        {
            m_count = new size_t(1);
        }

        ~MyAutoPtr()
        {
            --(*m_count);
            if (*m_count == 0)
            {
                delete m_count;
                delete m_ptr;
                m_ptr = nullptr;
                m_count = nullptr;
            }
        }

        MyAutoPtr(const MyAutoPtr &autoPtr)
        {
            m_count = autoPtr.m_count;
            ++(*m_count);
            m_ptr = autoPtr.m_ptr;
        }

        MyAutoPtr(MyAutoPtr &&autoPtr)
        {
            m_ptr = autoPtr.m_ptr;
            m_count = autoPtr.m_count;
            ++(*m_count);
        }

        MyAutoPtr &operator=(const MyAutoPtr &autoPtr)
        {
            if (this == &autoPtr)
                return *this;
            if (this->m_ptr != nullptr)
                ~MyAutoPtr();
            this->m_ptr = autoPtr.m_ptr;
            this->m_count = autoPtr.m_count;
            ++(*this->m_count);
        }

        T *Get() const { return this->m_ptr; }

        T &operator*() { return *(this->m_ptr); }

        T *operator->() { return this->m_ptr; }

        size_t GetUseCount() const { return *(this->m_count); }
    };

    void Test()
    {
        MyAutoPtr<int> p(new int(5));
        cout << p.GetUseCount() << endl;
        cout << *p << endl;
        MyAutoPtr<int> p2 = p;
        cout << p.GetUseCount() << endl;
    }
}

// ============================================

int main()
{
    //_01::Test();
    //_02::Test();
    //_03::Test();
    //_04::Test();
    //_05::Test();
    //_06::Test();
    //_07::Test();
    //_08::Test();
    //_09::Test();
    //_10::Test();
    //_11::Test();
    //_12::Test();
    //_13::Test();
    //_14::Test();
    _15::Test_02();

    // TestForExercise::Test();
    // TestForRValue::Test();
    // TestForOverride::Test();
    // TestForSharedPtr::Test();
}